Our objective is to introduce Tagapastry as a viable solution for keyword searching in a Pastry network. To this end, our test strategy involves simulating a real-world environment and testing it against the requirements outlined in section \ref{sec:requirements}. 

\subsection{Test configuration}

Thresholds are chosen from a set of values that are low enough to allow the simulation index expansion and retraction without risking to overload the test system environment. The concret values are stated in the test results. The leafset size is set to 24, the default value set by FreePastry.
Component based testing uses JUnit 4.7.

\subsection{Component testing}
Component based testing seems to be the most fundamental testing that can be done from the developers or testers point of view. In order to test the fulfilment of the functional requirements defined in section \ref{sec:func_req}, the following set of low level have been derived:

The \texttt{IndexImpl} class is responsible for indexing data on a node. It maintains its own
index entries and decides about start of expansion and retraction algorithms, thus the following
minimum set of requirements.
\begin{description}
\item[REQ/1] \texttt{IndexImpl} must correctly determine whether its parent or subparent.
\item[REQ/2] \texttt{IndexImpl} must correctly return number of elements it currently contains.
\item[REQ/3] \texttt{IndexImpl} must start expansion procedure only after exceeding expansion limit.
\item[REQ/4] \texttt{IndexImpl} must correctly calculate number of entries with corresponding ranks.
\item[REQ/5] \texttt{IndexImpl} must correctly evaluate whether one of its child has changed its size.
\end{description}

The \texttt{IndexRelative} class represents a node in a hierarchy created by an index. Nodes identified
by instances of this class take part in expansion and retraction algorithms, it is critical
that based on their own state they are capable of sending or buffering messages.
\begin{description}
 \item[REQ/6] \texttt{Index Relative} must correctly maintain its buffer. Depending on its own state
all the messages should be either buffered or sent immediately. Buffer size shall be empty
after finishing processing the buffer.
\end{description}

The \texttt{TagFactory} class is one of the core classes and provides different \textit{factories} for 
creation of a tag. This class is closely related to the mentioned \texttt{IndexRelative} class.

\begin{description}
\item[REQ/7] \texttt{TagFactory} must correctly instantiate new tag.
\item[REQ/8] \texttt{TagFactory} must correctly create parent tag in relation to supplied tag.
\item[REQ/9] \texttt{TagFactory} must correctly create child tag based on supplied extension data.
\item[REQ/10] \texttt{TagFactory} must correctly update current tag based on tag's state.
\end{description}

The \texttt{ChildrenMapper} class is used for proper selection of an instance of \texttt{IndexRelative} class
based on the supplied extension. This class is tailored to the concept of node identification
in a Pastry ring.
\begin{description}
\item[REQ/11] \texttt{ChildrenMapper} must be properly initialized to the hexadecimal values upon creation.
\item[REQ/12] \texttt{ChildrenMapper} must correctly extract \textit{index} value based on supplied extension.	
\item[REQ/13] \texttt{ChildrenMapper} must not return any value different than \textit{NULL} upon incorrect input
data.
\end{description}

A detailed description of the test cases that cover REQ/1 to REQ/13 are listed in the appendix. %\ref{sec:testresultdata}. 
Testresults show that all test cases have been satisfied.


\subsection{Correctness testing}
\label{corrtest}
Section \ref{sec:func_req} specifies the functional requirements of the Tagapastry system. The following test cases have been designed to verify the fulfillment of the requirements:

\begin{description}
 \item[Test Case 1] The tag operation should return boolean information indicating success or failure
of tagging data under a specified tag name and a category. An index expansion operation should be
executed if the amount of data exceeds the defined threshold.
\item[Test Case 2] The untag operation should return boolean information indicating success or failure of
untagging data under specified keyword and category. Subsequent calls to the untag operation, for the same data item, should be reflected first in a lower value, that describes popularity of the data item, and / or to its complete removal from the system. An index retraction processes should be observed on certain nodes, if a number of items stored on these nodes falls below defined threshold.
\item[Test Case 3] The search operation should return all the data, that is stored in a system under a specified tag name and a category. 
\end{description}

For the complete result set and defined input values please refer to the appendix. %\ref{testresultdata-correctness}.

%Correctness of Tagapastry system has been defined in section \ref{func_req}. An idea is to prove
%that those criteria are satisfied in our system by execution of a few test cases.

%Correctness testing includes testing of the core functionality of the system. Special attention
%has been paid to the usage of distribution and retraction algorithms, as well as, to the corresponding 
%message flows. Since we work with an asynchronous system, it is difficult to state assertions. An idea %is 
%to introduce logging system that will help us trace message flows and based on obtained results 
%asses correctness of the system. 

%All testcases have been satisfied. For the result set please refer to appendix. %\ref{sec:testresultdata-correctness}. 

\subsection{Performance testing}

The following tests address the non-functional requirements in \ref{sec:non_func_req}. 

\subsubsection{Simulating a real-word environment}
\label{sec:sim_real_env}
A model based on which to populate the test environment with data was needed. We chose delicious.com \cite{delicious} as a model for several reasons. Firstly, it offers similar core functionalities, namely tagging, untagging and searching, all based on keywords. Secondly, it is widely used. At the time of writing it has around 5 million users \cite{delicious5}.

Despite having no access to Delicious's operational statistics, we obtained the 199 most popular keywords including their associated number of entries~\cite{delicious199}. By applying linear regression on this data, we generated a best-fitting function that returns the approximate number of entries tagged under the $x$-th most populated keyword in the system, where 0 is the most popular keyword, 1 is the second, and so on.

\[r_{delicious}(x) = 21591 - 883x, x > 0 \]

\begin{figure}
 \includegraphics[keepaspectratio=true,width=\linewidth]{graphics/data_modelling.eps}
 %\caption{Standard deviation in load in relation to threshold.}
 \caption{A comparison of our linear modelling approach against the conjectured real shape of the data}
 \label{fig:data_shape}
\end{figure}

The fault of this approach is the assumption that the decrease in the number of entries is linear. We conjecture that in reality the population of indexes decreases at a increasing rate, so a best-fitting reciprocal function may be more suitable as a model. A contrast of the two different approaches is illustrated in figure \ref{fig:data_shape}. As shown, we believe that our current model underestimates the number of indexes in the system. Nevertheless, it suffices for now as we only require an approximation for our tests.

Our test environment can simulate up to $5000$ nodes within an acceptable time. Therefore, we cannot simulate millions of peers as simulating a system of Delicious's magnitude would require. Therefore, we scale down both the number of users and data in the system. We also assume that 20\% of the total number of users of a Tagapastry system would be on-line simultaneously. Thus, given a total user base of $25000$, approximately $5000$ nodes should be on-line. Based on this, we scale down delicious's data what it may have been like if Delicious had $25000$ users. We then test how $5000$ nodes handle this amount of data. The adjustment to the data-generation function are as follow:

\begin{eqnarray}
 f_{scale} & = & \frac{\textit{No. of overall users simulation}}{\textit{No. of overall users "delicious"}} \nonumber \\ 
 & = & \frac{25000}{5000000} = 0.005 \nonumber
\end{eqnarray} 
and thus \[r_{simulation}(x)=f_{scale}\times r_{delicious}(x)\]

To generate data, we iterated through this function for all $r_{simulation}(x) > 0$ and for every $x$ create an index with an arbitrary but unique keyword and populate it with $r_{simulation}(x)$ entries. 
\label{sec:test-correctness-results}

%Figure \ref{fig:avgload} shows average load distribution per node in the context of
%different thresholds. We can see that average load, which is expressed in bytes
%grows slightly together with higher threshold values. This makes sense, because
%higher threshold values indicate that a node can store more objects before it
%gets expanded. We can also see that this growth is not stable and in certain circumstances
%(around threshold 6000) the average load is much higher than the average load for other
%thresholds.

\subsubsection{Analysis of results}
\label{sec:analysis_of_results}

\begin{figure}
 \includegraphics[keepaspectratio=true,width=\linewidth]{test_results/stdev_load.eps}
 %\caption{Standard deviation in load in relation to threshold.}
 \caption{The spread of storage load with respect to the degree of distribution.}
 \label{fig:stdevload}
\end{figure}

Figure \ref{fig:stdevload} illustrates the affect of the degree of index distribution achieved by different sizes of the expansion threshold on the spread of data, measured in the standard deviation\footnote{ defined by $s=\sqrt{ \frac{1}{1-N} \sum_{i=o}^N(x_i-\bar{x})^2}$ where $N$ is the number of test samples, $x_i$ the measured test sample value $i$ and $\bar{x}$ the mean of the sample values} of the number of bytes stored at every node. As shown, the spread tends to increase considerably with the threshold. This shows that we are able to manage storage equality by adjusting the size of the threshold.

\begin{figure}
 \includegraphics[keepaspectratio=true,width=\linewidth]{test_results/avg_band.eps}
 %\caption{Average bandwidth usage per node in relation to threshold.}
 \caption{Local bandwidth with respect to the degree of distribution.}
 \label{fig:avgband}
\end{figure}

Figure \ref{fig:avgband} illustrates the affect of the degree of index distribution achieved by different sizes of the expansion threshold on the average bandwidth required by the system. As shown, the average bandwidth is inversely proportional to the threshold. We ignore the last anomalous three points for now. The shape of the graph makes sense because with a greater degree of distribution, more messages are required for maintenance, forwarding tag and untag messages and traversing the index for searching. 



\begin{figure}
 \includegraphics[keepaspectratio=true,width=\linewidth]{test_results/avg_delay.eps}
 %\caption{Average delay when searching data in relation to threshold}
 \caption{Search latency with respect to the degree of distribution}
 \label{fig:avgdelay}
\end{figure}

Figure \ref{fig:avgdelay} illustrates the affect of the degree of index distribution achieved by different sizes of the expansion threshold on search latency. Search latency tends to increase the more distributed indexes are. This is because the smaller the threshold is, the more levels of children indexes have, so search messages are routed through more nodes before arriving at indexes' leaves. 

From figure \ref{fig:stdevload}, we observe that decreasing the threshold from 8500 to 500 has considerable effect on the degree of distribution. Nevertheless, the average bandwidth only increases by around 27\%, and the percentage difference between the lowest and highest average search latencies is approximately 19\%.

This increase in average bandwidth and search latency is the trade-off of storage distribution. Thus, figures \ref{fig:stdevload}, \ref{fig:avgband} and \ref{fig:avgdelay} conjointly allow choosing an optimal threshold. A threshold of 4000-6000 seems to achieve a considerable degree of distribution with an acceptable trade-off. This is therefore our current recommendation. 

\subsubsection{Unexpected results}

\begin{figure}
 \includegraphics[keepaspectratio=true,width=\linewidth]{test_results/stdev_band.eps}
 %\caption{Standard deviation in bandwidth usage in relation to threshold.}
 \caption{Spread of bandwidth with respect to the degree of distribution.}
 \label{fig:stdevband}
\end{figure}

Figure \ref{fig:stdevband} illustrates the affect of the degree of index distribution achieved by different sizes of the expansion threshold on bandwidth evenness, measured by the sample standard deviation of the amount of bytes sent and received by each node. As shown, bandwidth evenness is disproportional to the expansion threshold. This graph does not look as we expected. We anticipated the bandwidth evenness to decrease the smaller the expansion threshold is. The reasoning is as follow. 

For an infinite expansion threshold, every index is stored on one node. Thus, bandwidth evenness should be extremely low as only one node is responsible for handling all messages addressed to the index. With distribution, indexes span more nodes, so messages addressed at the index also span more nodes. Thus, bandwidth equality should become more equal. 
Investigating the cause for the graph's shape should be the subject of future work. It may be a fault of the data model explained in \ref{sec:sim_real_env}.

